package everyday;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class T1054 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        int n = barcodes.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int[] p = pq.poll();
            if (i != 0 && p[0] == res[i - 1]) {
                int[] next = pq.poll();
                pq.offer(p);
                p = next;
            }
            res[i] = p[0];
            p[1] = p[1] - 1;
            pq.offer(p);
        }
        return res;
    }
}
